package pro.softzhang.algo.lc200;

import java.util.TreeSet;

public class LC220_ContainsDuplicateIII {
    public static void main(String[] args) {

    }

    static class Solution {
        public boolean containsNearbyAlmostDuplicate(int[] nums, int k, int t) {
            TreeSet<Long> s = new TreeSet<>();
            for (int i = 0; i < nums.length; i++) {
                Long lower = s.floor((long)nums[i]);
                if(lower != null && lower >= (long)nums[i] - t) {
                    return true;
                }

                Long upper = s.ceiling((long)nums[i]);
                if(upper != null && upper <= (long)nums[i] + t) {
                    return true;
                }

                s.add((long)nums[i]);

                if(i >= k) {
                    s.remove((long)nums[i - k]);
                }
            }
            return false;
        }
    }
}